When a resource on a communication network suffers a fault, it can automatically be remedied if a dedicated backup resource has been assigned in advance to a task which is using the resource and there are available a means for detecting a fault and a means for switching to the backup resource.
However, the assignment of dedicated backup resources to all tasks is problematic because it is necessary to have as many backup resources as or more backup resources than active resources available, making the cost of resources high. One effective solution to the problem is to reduce the total number of required resources by sharing backup resources among a plurality of tasks.
If a backup resource is shared by a plurality of tasks, then when the tasks suffer a fault at the same time, one of the faulty tasks can be remedied though the other tasks cannot be remedied. Therefore, if a backup resource is shared by a plurality of tasks, then the probability of recovery is lower than if dedicated backup resources are available for respective tasks. For preventing the probability of recovery from being lowered, it is effective to avoid the sharing of a backup resource between tasks which are highly likely to be simultaneously susceptible to failure.
Backup resource assignment processes based on such principles have been actively studied in the field of backbone communication infrastructure designs whose fault solutions tend to have large social and economical impacts. In particular, attention has been drawn in recent years to a backup route setting technology based on SRLG (Shared Risk Link Group) wherein communication resources which are highly likely to suffer a fault simultaneously are grouped together. SRLG refers to a group of resources which are simultaneously disabled by a single faulty event.
Insofar as tasks use backup resources which recover different tasks, but do not use resources belonging to the same SRLG as active resources, it is possible to avoid a conflict of recovery resources in the even of a single fault. Non-patent document 1 reveals that under such a condition, the complexity of a problem for assigning backup resources for overall optimization is NP-complete.
Non-patent document 2 proposes a scheme for calculating a resource utilization plan in a realistic calculation time by limiting possible combinations and hierarchizing resources so that they can be dissolved into small-scale problems.
The above examples are known examples relating to an intensive solution for a single process to calculate a resource assigning optimizing problem, in case that a list of utilization tasks relative to all SRLGs addressed by the problem can be known.
However, depending on one calculation process for the route determining function results in a vulnerability of the network managing function. To avoid such a drawback, it is desirable to employ a distributed backup route setting scheme where the management process of each task individually determines a backup resource. Non-patent document 3 proposes a distributed shared backup route setting scheme where tasks are communication paths and the task management process is a source node of each of the communication paths.
In order for a starting node to set a backup path capable of guaranteeing a recovery for a single fault, it is necessary to collect and hold the information of a band assigned to recover each SRLG from all resources to be searched for (only links are dealt with in Non-patent document 3). The amount of information to be held by the source node is on the order of the square of the number of resources on the entire network. Therefore, on large-scale networks, the exchange of information is likely to put pressure on the band and the processing capability.
In either one of the above examples, since the same recovery path is provided against a fault of any SRLGs through which the active communication path runs, only resources which do not belong to any SRLGs are selected as backup resources.
If backup resources are individually selected for SRLGs through which the active communication path runs, then it is possible to assign resources with higher efficiency. Non-patent document 4 proposes a process of selecting a backup resource such that a node for setting the backup resource will recover a fault of all SRLGs with a combination of recovery paths.
In this example, however, a node for selecting resources needs to hold information on the order of the square of the number of resources. If the resources are incorporated in a distribution fashion on a large-scale network, then the exchange of information is likely to put pressure on the band and the processing capability.
In the above examples, the problems posed when resources with SRLGs not overlapping those of active resources are selected as backup resources which a certain task can share with other tasks have been pointed out. In order to start using a selected resource or reserve a selected resource as a backup resource, a signaling process for the selected resource is required. For example, RSVP-TE (Non-patent document 5) is known as a signaling scheme for acquiring resources. Such a signaling scheme is applicable to the reservation of active resources which is to be carried out prior to the start of communications.
The reservation of a backup resource is permitted on the condition that a band required to recover an SRLG with the same resource will not exceed the capacity that can be used as the backup resource upon the reservation. To judge the capacity, it is necessary to have information as to what active resource is acquired by the task to be remedied. Since such information is held by a node which has selected a resource, if the selection of backup resources disclosed in Non-patent documents 3, 4 is incorporated in a distributed fashion, the information may be included in a backup resource reservation request message. A resource reservation signaling protocol including such an expansion is proposed in Non-patent document 6 and Patent document 1.
However, either of the examples is disadvantageous in that since all the signaling of active and backup resources needs to be finished before a task for guaranteeing a recovery for a single fault starts to be used, the delay from the sending of a request to the start of use of the task is large. Furthermore, aside from the above problem of the band consumed by the exchange of information about a resource state, there is a problem in that when many requests are coming in, the signaling traffic tends to put pressure on the communications and the processing capability.
In order that a backup resource that can be shared with other tasks is used to execute a fault recovery, a signaling process for determining which one of a plurality of tasks that is to be remedied will use the backup resource is needed even if the backup resource is reserved. At this time, if a plurality of recovery paths are defined as disclosed in Non-patent document 4, then a node for activating a recovery process has to identify an SRLG which has suffered a fault in order to determine which one of the recovery paths is to be used to recover the fault. If RSVP-TE is applied simultaneously to the recovery paths, not just to one recovery path, then the recovery time will be long due to a conflict of resources and the band will be consumed greatly by signaling messages. The difficulty may be avoided by using a signaling scheme having a scope including a plurality of paths, as disclosed in Patent document 2.
However, the above solution poses problems in that a node (a source node or a destination node) for activating a recovery process needs to be uniquely determined with respect to a communication path and, if a node which has detected an SRLG fault is far from a recovery process activation node owing to a communication path with a high hop count, then the consumption of time and a band for indicating the fault to the recovery process activation node are significant.
To make communication tasks highly reliable, there has been studied a scheme for recovering each transmission span of different communication paths that are multiplexed, rather than each task as a communication path (Non-patent document 7). However, since one recovery link is assigned to all tasks using resources in the span in question, resources are selected inefficiently for some tasks, and resource utilization efficiency on the overall network is lower than with the examples of Non-patent documents 1 through 4 (Non-patent document 8).
Non-patent document 1: S. Yuan and J. P. Jue, “Dynamic Lightpath Protection in WDM Mesh Networks under Risk-Disjoint Constraints,” in Proceedings of IEEE Globecom 2004, pp. 1770-1774 (2004);
Non-patent document 2: H. Matsuura, N. Murakami, K. Takami, “Disjoint SRLG Routing for GMPLS Networks by Hierarchically Distributed PCE,” IEICE Trans. Commun., Vol. E90-B, No. 1, pp. 51-61 (2007);
Non-patent document 3: E. Bouillet and J.-F. Labourdette, “Distributed Computation of Shared Backup Path in Mesh Optical Networks Using Probabilistic Methods,” IEEE/ACM Transactions on Networking, Vol. 12, No. 5, pp. 920-930 (2004);
Non-patent document 4: Z.-Li Tang and X.-M. Li, “A Mixed Shared and Multi Paths Protection Scheme with SRLG Constraints,” in Proceedings of 8th ACIS Intl Conf. on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, pp. 60-65 (2007);
Non-patent document 5: “RSVP-TE: Extensions to RSVP for LSP Tunnels,” RFC3209;
Non-patent document 6: “Signaling Extension for the End-to-End Restoration with SRLG,” internet draft, draft-choi-ccamp-e2e-restoration-srig-01.txt;
Non-patent document 7: “Generalized Multi-Protocol Label Switching (GMPLS) Recovery Functional Specification,” RFC4426;
Non-patent document 8: “Analysis of Generalized Multi-Protocol Label Switching (GMPLS)-based Recovery Mechanisms (including Protection and Restoration),” RFC4428;
Non-patent document 9: “Traffic Engineering (TE) Extensions to OSPF Version 2,” RFC3630;
Patent document 1: JP NO. 2007-129782A
Patent document 2: U.S. Pat. No. 7,289,450